package org.linuxsogood.boot.test;

/**
 * @author honway.liu
 * @date 2019-07-16 22:45
 * @email gm100861@gmail.com
 * @blog http://linuxsogood.org
 * 有一个非空整形数组，除了有一个只出现过一次的数，
 * 其他的数都出现且只出现过两次，现要求找出这个只出现过一次的数。
 * 时间复杂度不能超过 O(n)，而且不能使用额外空间。
 *
 * 两个相同元素的异或运算结果为 0，而 0 和其他元素的异或运算结果为该元素本身
 */
public class ArrayFindOneTimesNum {
    public static void main(String[] args) {
        System.out.println(1<<23);
        int[] arr = new int[]{1, 1, 4, 4, 3, 3, 7, 7, 8, 8, 2, 2, 10, 10, 199};
        System.out.println(singleNum(arr));
    }

    private static int singleNum(int[] arr) {
        int res = 0;
        for (int i : arr) {
            res ^= i;
        }
        return res;
    }
}
